﻿// 204. 表达整数的奇怪方式.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
/*

https://www.acwing.com/problem/content/206/

给定 2n 个整数 a1,a2,…,an 和 m1,m2,…,mn，求一个最小的非负整数 x，满足 ∀i∈[1,n],x≡mi(mod ai)。

输入格式
第 1 行包含整数 n。

第 2…n+1 行：每 i+1 行包含两个整数 ai 和 mi，数之间用空格隔开。

输出格式
输出最小非负整数 x，如果 x 不存在，则输出 −1。
如果存在 x，则数据保证 x 一定在 64 位整数范围内。

数据范围
1≤ai≤2^31−1,
0≤mi<ai
1≤n≤25
输入样例：
2
8 7
11 9
输出样例：
31
*/



#include <iostream>

using namespace std;

typedef long long LL;


int n;
const int N = 30;
long long  a[N], m[N];



long long exgcd(long long a, long long b, long long& x, long long& y) {
	if (!b) {
		x = 1, y = 0;
		return a;
	}

	long long d = exgcd(b, a % b, x, y);
	long long t = y;
	y = x - a / b * y;
	x = t;

	return d;
}

 
int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i] >> m[i];
	}
	
	long long a01 = a[1]; long long m01 = m[1];
	long long x = m01 % a01;
	for (int i = 2; i <= n; i++) {
		long long k1, k2;
		long long a02 = a[i]; long long m02 = m[i];
		long long d = exgcd(a01, -a02, k1, k2);
		if ((m02 - m01) % d) {
			x = -1; break;
		}
		k1 *= (m02 - m01) / d;
		long long t = abs(a02 / d);
		k1 = (k1 % t + t) % t;
		x = k1 * a01 + m01;
		m01 = x;
		a01 = abs(a01/ d*a02);
	}

	cout << x << endl;


	return 0;
}

 